1795F - Blocking Chips - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
int t,n,x,y,g[1<<20],k,a[1<<20],l,r,d,v;
vector<int>e[1<<20]; 
int D(int x,int f){
	int p=g[x],q=0,r;
	for(int y:e[x])
		if(y^f){
			r=D(y,x);
			if(r<0&&p)
				return v=0;
			r<0?p=-r:q=max(q,r);
		}
	if(!p)
		return q+1;
	if(p<=q+1)
		return 0;
	return -p+1;
}
int C(int x){
	for(int i=1;i<=k;i++)
		g[a[i]]=(x+k-i)/k+1;
	v=1,v&=D(1,0)>=0;
	return v;
}
main(){
	cin>>t;
	while(t--&&cin>>n){
		for(int i=1;i<=n;i++)
			e[i].clear(),g[i]=0;
		for(int i=1;i<n;i++)
			cin>>x>>y,e[x].push_back(y),e[y].push_back(x);
		cin>>k,l=0,r=n;
		for(int i=1;i<=k;i++)
			cin>>a[i];
		while(l<r)
			d=(l+r+1)/2,C(d)?l=d:r=d-1;
		cout<<l<<'\n';
	}
}